/**
 * https://leetcode-cn.com/problems/longest-increasing-subsequence
 * 最长递增子序列
 * @param nums 
 */

const lengthOfLIS = (nums: number[]): number => {
    // [10, 9, 2, 5, 3, 7, 101, 18]

    let len = 0;
    const sortedArr: number[] = []
    const sortedIndexArr: number[] = []
    for (let i = 0; i < nums.length; i++) {
        let v = nums[i]

        // 只需要找len长度即可, 找到比v大的索引位置
        // 首次不用找
        let s = 0, e = len;
        while (s < e) {
            const m = (s + e) >> 1;
            if (sortedArr[m] >= v) {
                // 比当前元素大, 往前
                e = m
            } else {
                // 比当前元素小, 往后
                s = m + 1;
            }
        }
        // s 就是第一个比元素大的位置
        // 同时由于找到比第一个大得元素的位置, 会覆盖哪个元素, 因为它更有潜力
        sortedArr[s] = v
        sortedIndexArr[s] = i
        // 如果找到了尾部, 说明要递增
        if (s === len) len++
    }
    console.log(sortedArr)
    console.log(sortedIndexArr)
    return len;
};

// O(n ^ 2)
const lengthOfLIS2 = (nums: number[]): number => {
    // [10, 9, 2, 5, 3, 7, 101, 18]
    // [1, 1, 1, 2, 2, 3, 4, 4]

    // dp[i] 以下标i底的最长递增子序列长度
    // 状态转移方程: dp[i] = nums[i - k] > nums[i] ? max{nums[i - k]} : 1 即找到i 前面的比当前元素小的元素后 + 1, 取这些长度的最大值
    const len = nums.length;
    const dp: number[] = new Array(len).fill(1)

    // 默认为1
    let max = 1;

    for (let i = 1; i < len; i++) {
        // 遍历0 ~ i 之前的元素, 如果比当前的元素小, 那么加1, 并且取长度为最大的
        let m = 1 // 存放之前长度+1的最大值, 最后赋给dp[i]
        const cur = nums[i]
        for (let j = 0; j < i; j++) {
            if (nums[j] < cur) {
                m = Math.max(dp[j] + 1, m)
            }
        }
        // 如果前面有比当前元素大的, 就更新 
        // 如果没有比当前元素大的, 不用处理, 数组默认元素就是-1
        if (m !== 1) {
            dp[i] = m
            max = Math.max(m, max)
        }
    }

    return max
};

/**
 * vue 最长递增子序列, 求索引的
 * @param arr 
 * @returns 
 */
const getSequence = (arr: number[]): number[] => {
    // [2, 5, 9, 3, 7]
    // 拷贝arr
    const p = arr.slice()

    // result存放的是递增的元素索引
    const result = [0]

    let i, j, u, v, c
    const len = arr.length

    // 遍历
    for (i = 0; i < len; i++) {
        const arrI = arr[i]
        // 数组值为0的不处理
        if (arrI !== 0) {
            // 取出最后一项, 即数组的索引
            j = result[result.length - 1]

            // 当前元素比result最后一项大
            if (arr[j] < arrI) {
                // 存放比arrI大的索引, j 为 比i大的索引
                //! p[i] 表示比i位置小的元素的索引
                p[i] = j
                // p: [1, 0, 7] result: [0, 1]
                // p: [1, 0, 1] result [0, 1, 2]

                // 放入 result中
                result.push(i)

                // 结束当前循环
                continue
            }

            // 二分查找, 找到第一个比arrI大的元素索引
            u = 0
            v = result.length - 1
            while (u < v) {
                // 获取中间位置索引
                c = (u + v) >> 1

                // 当前元素比中间元素大
                if (arr[result[c]] < arrI) {
                    // 往后找
                    u = c + 1
                } else {
                    // 往前找
                    v = c
                }
            }

            // u 就是要找的位置
            if (arrI < arr[result[u]]) {
                // 比arrI大的索引大于0
                if (u > 0) {
                    // 比i 小的元素的位置就是u-1, 因为u是大于或等于arrI的
                    p[i] = result[u - 1]
                }
                // i更有潜力, 替换u的位置, 后面继续找比i位置大的元素
                result[u] = i
            }
        }
    }

    // result的长度
    u = result.length

    // 取出result最后一项
    v = result[u - 1]

    // 从后往前覆盖
    while (u-- > 0) {
        result[u] = v
        // p[v] 找到比索引v小的元素的索引
        v = p[v]
    }
    return result
}

// console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))
console.log(getSequence([10, 9, 2, 5, 3, 7, 101, 18]))
// console.log(lengthOfLIS([2, 2, 2, 2]))